class NumSquares:
    def solve(self, n):
        """
        计算和为n的最少完全平方数数量
        :param n: 目标数字
        :return: 最少完全平方数数量
        """
        dp = [float('inf')] * (n + 1)
        dp[0] = 0  # 基本情况

        for i in range(1, n + 1):
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1

        return dp[n]